package j2024.j202407;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class j0718 {
    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0};
    boolean[][] vis;
    char[] w;
    int m,n;
    public boolean exist (String[] board, String word) {
        // write code here
        w = word.toCharArray();
        m = board.length;
        n = board[0].length();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i].charAt(j)==w[0]){
                    if(bfs(board,i,j,0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public boolean bfs(String[] board,int i,int j,int v){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{i,j});
        vis[i][j] = true;
        while(!q.isEmpty()){
            int[] tmp = q.poll();
            int a =  tmp[0],b  = tmp[1];
            for (int k = 0; k < 4; k++) {
                int x = a+dx[i];
                int y = b+dy[i];
                if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && board[x].charAt(y)==w[v]){
                    if(v==w.length-1){
                        return true;
                    }
                    v++;
                    q.add(new int[]{x,y});
                    vis[x][y] = true;
                }
            }
        }
        return false;
    }
//    public static int[] dx = {0,0,-1,1};
//    public static int[] dy = {1,-1,0,0};
//    public static boolean exist (String[] board, String word) {
//        // write code here
//        int m = board.length,n = board[0].length();
//        char[][] str = new char[m][n];
//        char[] w = word.toCharArray();
//        for (int i = 0; i < board.length; i++) {
//            str[i] = board[i].toCharArray();
//        }
//        Queue<int[]> q =new LinkedList<>();
//        int[][] vis = new int[m][n];
//
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if(str[i][j]==w[0]){
//                    q.add(new int[]{i,j});
//                    vis[i][j]=1;
//                }
//            }
//        }
//        int v = 1;
//        while(!q.isEmpty()){
//            int[] tmp = q.poll();
//            int a = tmp[0],b = tmp[1];
//            for (int i = 0; i < 4; i++) {
//                int x = a+dx[i],y = b+dy[i];
//                if(x>=0 && x<m && y>=0 && y<n && vis[x][y]!=1 && str[x][y] ==w[v] &&v<w.length){
//                    v++;
//                    q.add(new int[]{x,y});
//                    vis[x][y] = 1;
//                }
//            }
//        }
//        if(v== w.length-1){
//            return true;
//        }else {
//            return false;
//        }
//    }

    public static void main(String[] args) {
        String[] x = {"XYZE","SFZS","XDEE"};
        String w = "XYZZED";
        //boolean a = exist(x,w);
    }
    public static void main2(String[] args) {
        Scanner in  = new Scanner(System.in);
        int n = in.nextInt();
        int[][] ret = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if(j==0||j==i){
                    ret[i][j] = 1;
                }else {
                    ret[i][j] = ret[i-1][j]+ret[i-1][j-1];
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                System.out.printf("%5d",ret[i][j]);
            }
            System.out.println();
        }
    }
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int fib = in.nextInt();
        int a = 0,b = 1;
        if(fib==a||fib==b){
            System.out.println(0);
        }
        int f = 0;
        int left = 0,right = 0;
        while(true){
            f = a+b;
            a=b;
            b=f;

            if(f<=fib){
                left = f;
            }else{
                right = f;
                break;
            }
        }
        System.out.println(Math.min(fib-left,right-fib));
    }
}
